import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lenovo
 * Date: 2023-02-22
 * Time: 20:27
 */
public class Test1 {
    /**
     * 使用map O(n)
     *
     * @param array
     */
    private static void mapFun(int[] array) {
        Map<Integer, Integer> map = new HashMap<>();
        //将数组里的数据全部都放入到map里
        for (int i = 0; i < array.length; i++) {
            int value = map.getOrDefault(array[i], -1);
            if (value == -1) {
                map.put(array[i], 1);
            } else {
                map.put(array[i], value + 1);
            }
        }
        //通过entry来遍历map里的元素,找出value等于1的数字并返回
        Set<Map.Entry<Integer, Integer>> entrySet = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entrySet) {
            if (entry.getValue() == 1) {
                System.out.println(entry.getKey());
            }

        }
    }

    /**
     * O(n)
     *
     * @param array
     */
    private static void setFun(int[] array) {
        Set<Integer> set = new HashSet<>();
        //遍历数组,将数组里的元素放进set里,出现两次的数字户被删除,最终只剩下出现了一次的数字
        for (int i = 0; i < array.length; i++) {
            if (!set.contains(array[i])) {
                set.add(array[i]);
            } else {
                set.remove(array[i]);
            }

        }
        //由于set集合太大,因此不直接遍历set集合,而是再次遍历数组,由于即即合理只存在出现了一次的数字,因此只要对数组里的元素在集合里进行判断,如果数组里的数字存在于集合里就是只出现一次的数字
        for (int i = 0; i < array.length; i++) {
            if (set.contains(array[i])) {
                System.out.println(array[i]);
            }
        }
    }


    /**
     * 使用异或 O(n)
     *
     * @param
     */
    private static void xorFun(int[] array) {
        int ret = 0;
        for (int i = 0; i < array.length; i++) {
            ret ^= array[i];
        }
        System.out.println(ret);
    }

    public static void main1(String[] args) {
        int[] array = new int[]{1, 2, 2, 1, 3};
        mapFun(array);
        setFun(array);
        xorFun(array);


    }

    /////////////////////////////////////////////
    ////////////////////////////////////////////

    /**
     * 复制随机链表:https://leetcode.cn/problems/copy-list-with-random-pointer/
     */
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        //这里不能使用treemap,因为treemap必须得能比较大小
        Map<Node, Node> map = new HashMap<>();
        //map(key->旧的节点地址:value->新的节点地址)
        Node cur = head;
        //cur第一遍遍历,new新节点,并且将旧节点的val值复制到新的节点里
        while (cur != null) {
            Node node = new Node(cur.val);
            ////map(key->旧的节点地址:value->新的节点地址)
            map.put(cur, node);
            cur = cur.next;
        }
        //cur第二遍循环,将新的节点的next和random按照旧的节点的next和random进行连接
        cur = head;
        while (cur != null) {
            //map.get(cur)这个就是根据map的key获取到对应的value,而这里的value值为新节点node:node.next
            //map.get(cur.next)这个就是cur指向的当前节点的下一个节点对应的新产生的node
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //遍历新链表,头结点是一直没有动的
        return map.get(head);


    }


    ///////////////////////////////////////
    //////////////////////////////////////

    /**
     * 石头里有多少宝石:https://leetcode.cn/problems/jewels-and-stones/
     */

    //使用map
    public int numJewelsInStones(String jewels, String stones) {
        Map<Character, Integer> map = new HashMap<>();
        //将全部的宝石放进map里面
        for (int i = 0; i < jewels.length(); i++) {
            map.put(jewels.charAt(i), 0);
        }
        for (int i = 0; i < stones.length(); i++) {
            //石头里面包含宝石,更新数量
            if (map.containsKey(stones.charAt(i))) {
                int count = map.get(stones.charAt(i));
                map.put(stones.charAt(i), count + 1);
            }

        }
        //统计map里的count和
        int sum = 0;
        Collection<Integer> collection = map.values();
        for (Integer count : collection) {

            sum += count;
        }
        return sum;


    }

    //暴力破解
    public int numJewelsInStones1(String jewels, String stones) {
        int count = 0;
        //外层循环比较的趟数
        for (int i = 0; i < jewels.length(); i++) {
            //内层循环每趟比较的次数
            for (int j = 0; j < stones.length(); j++) {
                //如果是宝石,count++
                if (jewels.charAt(i) == stones.charAt(j)) {
                    count++;
                }


            }

        }
        return count;
    }

    //使用set
    public int numJewelsInStones2(String jewels, String stones) {
        Set<Character> set = new HashSet<>();
        //这里的循环将全部的宝石放进集合里
        for (Character c : jewels.toCharArray()) {
            set.add(c);
        }
        //计数器
        int count = 0;
        //这里的循环时查看石头里面有多少个宝石
        for (Character c : stones.toCharArray()) {
            if (set.contains(c)) {
                count++;
            }
        }
        return count;
    }


    /////////////////////////////////////
    //////////////////////////////////////

    /**
     * 坏键盘打字:https://www.nowcoder.com/questionTerminal/f88dafac00c8431fa363cd85a37c2d5e
     */

    static void fun(String str1, String str2) {
        //将实际输出的字符全部放到set里
        Set<Character> setAC = new HashSet<>();
        for (Character c : str2.toUpperCase().toCharArray()) {
            setAC.add(c);
        }
        //遍历预期输出的字符串,setAC 里不存在的字符即为坏掉的键盘
        Set<Character> setBAd = new HashSet<>();
        for (Character c : str1.toUpperCase().toCharArray()) {
            //setExpect里不包含c,说明c是坏掉的键盘
            if (!setAC.contains(c) && !setBAd.contains(c)) {
                //题目要求只打印字符,且不换行,因此只能这样打印
                System.out.print(c);
                //setBAd用来判断去重
                setBAd.add(c);
            }
        }
        //toString格式的打印
//        String badC = setBAd.toString();
//        System.out.println(badC.toUpperCase());
//        System.out.println(setBAd);

    }

    public static void main233(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String s1 = sc.nextLine();//期望输入的
            String s2 = sc.nextLine();//实际输入的
            fun(s1, s2);
        }


    }


    /////////////////////////////
    /////////////////////////////
    /**
     * 前k个高频单词:https://leetcode.cn/problems/top-k-frequent-words/
     */
//    public List<String> topKFrequent(String[] words, int k) {
//        Map<String,Integer> map = new HashMap<>();
//        //将words里的全部字符串都放进map里
//        for (String s: words) {
//            int value = map.getOrDefault(s,-1);
//            //map里不存在
//            if(value ==-1){
//                map.put(s,1);
//            }else{//map里存在s,更新value
//                map.put(s,map.get(s)+1);
//            }
//        }
//
//
//    }










    /////////////////////////////
    //////////////////////////////
    /**
     * 第一个只出现一次的字符:https://leetcode.cn/problems/first-unique-character-in-a-string/
     */
    //使用hash函数的思想:key-a(97)
    public int firstUniqChar(String s) {
        int [] count = new int[26];
        //利用hash的思想,将字符串里的字符全部存储到数组里,数组里的元素为字符出现的次数
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i)-'a'] ++;
        }
        //遍历字符数组,在字符数组里寻找第一个只出现一次的字符
        for (int i = 0; i < s.length(); i++) {
            if(count[s.charAt(i)-'a'] == 1){
                return i;
            }

        }
        //循环走完还没找到
        return -1;

    }
    //使用map
    public int firstUniqChar1(String s) {
      Map<Character,Integer> map = new HashMap<>();
      //将字符串里的所有字符出现的次数统计到map里
        for (Character ch: s.toCharArray()) {
            if(map.get(ch) ==null){
                map.put(ch,1);
            }else{
                map.put(ch,map.get(ch)+1);
            }

        }
        //遍历字符串,直到第一个只出现一次的字符
        for (int i = 0; i < s.length(); i++) {
            if(map.get(s.charAt(i))==1){
                return i;
            }
        }
        return -1;

    }


}
